function mergeSort(arr) {
  let len = arr.length;
  if (len < 2) return arr;
  let mid = Math.floor(len / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));  // 切片，把数组切成，length为 1 的数组
}

/**
 * 排序并合并两个数组
 * 要求：两个数组内部必须是已经排好序的，如果数组中只有一个，那一定是排好的
 */
function merge(left, right) {
  let result = [];

  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());

  return result;
}

var arr = [3, 5, 7, 1, 4, 56, 12, 78, 25, 0, 9, 8, 42, 37];
var res = mergeSort(arr);
console.log(arr, res);

console.log(merge([3, 4, 44, 88, 100], [1, 22, 33, 78, 90]));
